package com.example.demo.linkedlist;

/**
 * 单链表的插入、删除、查找操作
 * 链表中存储的是int类型的数据
 * @auther lijiewei
 * @date 2021/8/16 17:13
 */
public class SinglyLinkedList {

    private Node head = null;

    /**
     * 根据值来查询
     * @param value 值
     * @return
     * @author lijiewei
     * @date   2021/8/16 17:30
     */
    public Node findByValue(int value) {
        Node preNode = head;
        while(preNode != null && preNode.getData() != value) {
            preNode = preNode.getNext();
        }
        return preNode;
    }

    /**
     * 根据序号来查询
     * @param index 序号
     * @return
     * @author lijiewei
     * @date   2021/8/16 17:30
     */
    public Node findByIndex(int index) {
        Node preNode = head;
        int pos = 0;
        while(preNode != null && pos != index) {
            preNode = preNode.getNext();
            pos++;
        }
        return preNode;
    }

    /**
     * 头部插入值
     * @param value 值
     * @return
     * @author lijiewei
     * @date   2021/8/16 17:46
     */
    public void insertToHead(int value) {
        Node newNode = new Node(value, null);
        if (head == null) {
            head = newNode;
        } else {
            newNode.setNext(head);
            head = newNode;
        }
    }

    /**
     * 尾部插入值
     * @param value 值
     * @return
     * @author lijiewei
     * @date   2021/8/16 17:53
     */
    public void insertTail(int value) {
        Node newNode = new Node(value, null);
        if (head == null) {
            head = newNode;
        } else {
            Node preNode = head;
            while(preNode.getNext() != null) {
                preNode = preNode.getNext();
            }
            preNode.setNext(newNode);
        }
    }

    /**
     * 在指定节点 node 之后插入
     * @param node 指定节点
     * @param value 值
     * @return
     * @author lijiewei
     * @date   2021/8/16 18:02
     */
    public void insertAfter(Node node, int value) {
        if(null == node || null == head) {
            return;
        }
        Node newNode = new Node(value, null);
        node.setNext(newNode);
    }

    /**
     * 在指定节点 node 之前插入
     * @param node 指定节点
     * @param value 值
     * @return
     * @author lijiewei
     * @date   2021/8/17 9:37
     */
    public void insertBefore(Node node, int value) {
        if(null == node || null == head) {
            return;
        }
        if(head == node) {
            insertToHead(value);
            return;
        }
        Node preNode = head;
        while(null != preNode && preNode.getNext() != node) {
            preNode = preNode.getNext();
        }
        //没找到
        if(null == preNode) {
            return;
        }
        Node newNode = new Node(value, null);
        newNode.setNext(node);
        preNode.setNext(newNode);
    }

    /**
     * 删除指定节点
     * @param node 指定节点
     * @return
     * @author lijiewei
     * @date   2021/8/17 9:58
     */
    public void deleteByNode(Node node) {
        if(null == node || null == head) {
            return;
        }
        if(head == node) {
            head.setNext(node.getNext());
            return;
        }
        Node preNode = head;
        while(null != preNode && preNode.getNext() != node) {
            preNode = preNode.getNext();
        }
        //没找到
        if(null == preNode) {
            return;
        }
        preNode.setNext(node.getNext());
    }

    /**
     * 根据value删除节点
     * @param value 值
     * @return
     * @author lijiewei
     * @date   2021/8/17 10:15
     */
    public void deleteByValue(int value) {
        if(null == head) {
            return;
        }
        Node node = head;
        Node preNode = null;
        while(node != null && node.getData() != value) {
            preNode = node;
            node = node.getNext();
        }
        //没找到
        if (null == node) {
            return;
        }

        if (null == preNode) {
            //value对应的是头节点
            head.setNext(head.getNext());
            return;
        } else {
            preNode.setNext(preNode.getNext().getNext());
        }



        if(head.getData() == value) {
            head.setNext(head.getNext());
            return;
        }

        while(null != preNode && preNode.getNext().getData() != value) {
            preNode = preNode.getNext();
        }
        //没找到
        if(null == preNode) {
            return;
        }
        preNode.setNext(preNode.getNext());
    }

    /**
     * 打印所有节点
     * @return
     * @author lijiewei
     * @date   2021/8/17 11:05
     */
    public void printAll() {
        Node node = head;
        while (null != node) {
            System.out.print(node.getData() + ",");
            node = node.getNext();
        }
        System.out.println();
    }

    /**
     * 判断是否为回文abcba
     * @return
     * @author lijiewei
     * @date   2021/8/17 13:58
     */
    public boolean palindrome() {
        //空链表
        if (head == null) {
            return false;
        }
        System.out.println("开始查找中间节点");
        Node preNode = head;
        Node sufNode = head;
        //只有一个节点
        if (null == preNode.getNext()) {
            return true;
        }
        while (null != preNode.getNext() && null != preNode.getNext().getNext()) {
            //一个节点一个节点走
            sufNode = preNode.getNext();
            //两个节点两个节点走
            preNode = preNode.getNext().getNext();
        }
        System.out.println("中间节点：" + sufNode.getData());
        Node leftLink = null;
        Node rightLink = null;
        if (null == preNode.getNext()) {
            //链表节点数目为奇数个
            rightLink = sufNode.getNext();
            leftLink = inverseLinkList(sufNode).getNext();
        } else {
            //链表节点数目为偶数个
            rightLink = sufNode.getNext();
            leftLink = inverseLinkList(sufNode);
        }
        return TFResult(leftLink, rightLink);
    }

    /**
     * 链表翻转 a->b->c ==> c->b->a 新建了一个链表
     * @param endNode 尾结点
     * @return
     * @author lijiewei
     * @date   2021/8/17 14:24
     */
    public Node inverseLinkList(Node endNode) {
        //遍历旧链表，取出结点通过头部插入的方式形成一条新链表
        //遍历旧链表的结点
        Node r = head;
        //遍历旧链表r的后一个结点
        Node next = null;
        //新链表上次插入的结点
        Node pre = null;
        while (r != endNode) {
            //遍历旧链表
            next = r.getNext();
            //向新链表中插入
            r.setNext(pre);
            pre = r;
            //遍历旧链表
            r = next;
        }
        r.setNext(pre);
        //此时r是新链表的头结点
        return r;
    }

    /**
     * 判断左右两个链表是否一致
     * @param left 左链表的开始结点
     * @param right 右链表的开始结点
     * @return
     * @author lijiewei
     * @date   2021/8/17 18:08
     */
    public boolean TFResult(Node left, Node right){
        Node l = left;
        Node r = right;
        boolean flag=true;
        while(l != null && r != null){
            if (l.getData() == r.getData()){
                l = l.getNext();
                r = r.getNext();
                continue;
            }else{
                flag=false;
                break;
            }

        }
        return flag;
    }
}
